#lang scheme
; TODO: rename to producer or generator ?
; TODO: make all of them (only -merge left) /deferred by default, add /now versions

; TODO: iter-permutations
; TODO: iter-combinations
; TODO: iter-power-set power-set-binary
; TODO: iter-cartesian-product
; TODO: iter-cartesian-product-right
; TODO: (iter-add-between '(x y z) 'or)

; TODO: iter-union <- iter-merge

; TODO: iter-average (providing + and /?)
; TODO: iter-argmin iter-argmax
; TODO: limit rate /bandwich ?
; TODO: limit time #:with-message
; TODO: iter-unfold (iter constructor)
; TODO: something from http://docs.python.org/library/itertools.html#itertools-functions
; TODO: iter-cycle
; TODO: iter-repeat
; TODO: iter-tee, then iter-span &co on top of iter-tee
; TODO: iter-groupby
; TODO: iter->stream
; TODO: stream->iter
; TODO: pattern matching on iter with 'put back' using (iter* a b it) ?
; TODO: fifo, for parallel iter-recur
; TODO: iter-recur -> iter-dfs
; TODO: iter-recur -> iter-bfs
; TODO: 'seq', like iter, returns (v, #f or lambda to get next), thus it has no state and is savable/copyable/etc
;        But it could be slower
; TODO: iter-remove-duplicates
(provide iter
         iter*
         iter-eof
         iter-eof?
         iter-null
         make-iter

         list->iter
         vector->iter
         bytes->iter
         bytes-u32->iter

         string->iter
         string->iter-ord
         iter-range
         iter-iota

         iter->list

         iter-take
         iter-drop
         iter-drop/now
         iter-take-while
         iter-drop-while/now
         iter-drop-while
         iter-index

         iter-append
         iter-append*

;         iter-parallel
         channel->iter
;         iter-channel
         iter-channel/oneeof
         iter-channel/eof-forever

         iter-lazy

         iter-map        ; srfi/1 behaviour
         iter-any
         iter-every
         iter-fold       ; srfi/1 behaviour
         iter-fold-right ; srfi/1 behaviour
         iter-filter
         iter-filter-map
         iter-reduce
         iter-reduce-right
         iter-zip
         iter-for-each
         iter-o

         iter-recur  ; directory walk helper

         iter-length ; that destroys the iter

         iter->tree
         iter->bintree
         iter-merge
         iter-mergev
         iter-merge*
         iter-intersection

         iter-min
         iter-max
         iter-minn
         iter-minn-unique

         iter-random-sample
         iter-random-samples
         iter-random-samples-unique


        iter-pmap/unsafe
        iter-syncronize
        iter-pmap
        read->iter

        ; monad
        iter-join
        iter-bind
         )



(require rnrs/sorting-6 scheme/mpair
         rnrs/bytevectors-6
         srfi/26
         srfi/27
         srfi/67
         srfi/71
         srfi/1
         mzlib/etc
         "test.ss"
         "tidbits.ss"
         "sorting.ss"
         )

; TODO:  (eof) to make it compatible with (read-*)
; TODO:  (void) to make it compatible with scheme/generator
(define iter-eof (gensym))
(define (iter-eof? it) (eq? iter-eof it))

(define iter-null (const iter-eof))

; a -> (a -> boolean) -> (a -> a) -> (a -> b) -> iter<b>
(define (make-iter ii stop? next read)
  (lambda()
    (if (stop? ii)
        iter-eof
        (begin0 (read ii)
                (set! ii (next ii))))))

;; list -> iter
(define (list->iter lst)
  (lambda() (if (null? lst)
                iter-eof
                (pop! lst))))

(define (iter . values)
  (list->iter values))

; like list*
;; v1 -> v1 -> ... -> iter -> iter
(define (iter* . its)
  (if (null? its)
      iter-eof
      (lambda() (if (null? (cdr its))
                    ((car its))
                    (pop! its)))))

;; iter -> list
(define (iter->list it)
  (let ([v (it)])
    (if (iter-eof? v)
        '()
        (cons v (iter->list it)))))

;; iter -> list
; tail-recursive
(define (iter->rlist it)
  (let loop ([rest '()])
    (let ([v (it)])
      (if (iter-eof? v)
          rest
          (loop (cons v rest))))))


;; iter -> number
(define (iter-length it)
  (let loop ([len 0])
    (if (iter-eof? (it))
        len
        (loop (add1 len)))))

; (iter-map ref-proc (iter-range start stop))
;; number -> number -> number -> iter<number>
(define (iter-map-range proc start end [step 1])
  (lambda() (if ((if (positive? step)>= <=) start end)
                iter-eof
                (begin0 (proc start)
                        (inc! start step)))))

(define (build-iter count proc)
  (let ([i 0])
    (lambda() (if (>= i count)
                  iter-eof
                  (begin0 (proc i)
                          (inc! i))))))


;; vector -> iter
(define (vector->iter vec [start 0] [end (vector-length vec)] [step 1])
  (iter-map-range (curry vector-ref vec) start end step))

;; bytes -> iter<byte>
(define (bytes->iter bstr [start 0] [end (bytes-length bstr)]) ; [step 1])
  (iter-map-range (curry bytes-ref bstr) start end))

;; string -> iter<char>
(define (string->iter str [start 0] [end (string-length str)]) ; [step 1])
  (iter-map-range (curry string-ref str) start end))

;; string -> iter<fxnum>
(define (string->iter-ord str [start 0] [end (string-length str)]) ; [step 1])
  (iter-map-range (lambda(i)(char->integer (string-ref str i))) start end))

;; bytes -> iter<number>
(define (bytes-u32->iter bstr [start 0] [end (bytes-length bstr)])
  (iter-map-range (curry bytevector-u32-native-ref bstr) start end 4))

; works with any kind of numbers
(define (iter-range start stop [step 1])
  (iter-map-range identity start stop step))

(define (iter-iota count [start 0] [step 1])
  (lambda() (if (positive? count)
                (begin0 start
                        (dec! count)
                        (inc! start step))
                iter-eof)))

;; iter -> number -> iter
(define (iter-take it n)
  (lambda() (if (positive? n)
                (let ([v (it)]) ; v can be iter-eof
                  (if (iter-eof? v)
                      (set! n 0)
                      (dec! n))
                  v)
                iter-eof)))

;; iter -> number -> iter
(define (iter-drop/now it n)
  (let loop ([n n])
    (when (positive? n)
      (if (iter-eof? (it))
          iter-null
          (loop (sub1 n)))))
  it)

;; iter -> number -> iter
(define (iter-drop it n)
  (lambda() (let loop ()
              (let ([v (it)])
                (cond [(iter-eof? v) iter-eof]
                      [(positive? n) (dec! n) (loop)]
                      [else v])))))

;; pred -> iter -> iter
(define (iter-take-while pred it)
  (lambda() (let ([v (it)])
              (if (iter-eof? v)
                  iter-eof
                  (if (pred v)
                      v
                      (begin (set! it iter-null)
                             iter-eof))))))

;; pred -> iter -> iter
(define (iter-drop-while/now pred it)
  (let loop ()
    (let ([v (it)])
      (if (iter-eof? v)
          iter-null
          (if (pred v)
              (loop)
              (iter* v it)))))) ; put v back

; with deferred consuming
;; pred -> iter -> iter
(define (iter-drop-while pred it)
  (lambda() (let loop ()
              (let ([v (it)])
                (cond [(iter-eof? v) iter-eof]
                      [(not pred) v]
                      [(pred v) (loop)]
                      [else (set! pred #f) v])))))

; pred -> iter -> integer | #f
(define (iter-index pred . its)
  (let loop ([i 0])
    (let ([vl (read-iters its)])
      (cond [(eq? #f vl) #f]
            [(apply pred vl) i]
            [else (loop (add1 i))]))))

; defer iter construction
;; (-> iter) -> iter
(define (iter-lazy ctor)
  (let ([it #f])
    (lambda()
      (unless it (set! it (ctor)))
      (it))))

;; pred -> iter -> (iter iter)
(define (iter-span pred it)
  (define itake-fifo #f) ; TODO: fifo
  (define vdrop iter-eof)

  (values
   ; take
   (lambda() (if itake-fifo
                 (itake-fifo)
                 (let ([v (it)])
                   (cond [(iter-eof? v) v]
                         [(pred v)      v]
                         [else (set! itake-fifo iter-null)
                               (set! vdrop v)
                               (set! pred #f)
                               iter-eof]))))
   ; drop
   (lambda() (if (eq? vdrop iter-eof)
                 (let ([v (it)])
                   (cond [(iter-eof? v)
                          ;(unless itake-fifo
                          ;  (set! itake-fifo iter-null))
                          iter-eof]
                         [(not pred)     v]
                         [(not (pred v)) (set! pred #f)
                                         v]
                         [else ; to fifo
                          (false! itake-fifo)
                          (let ([v4 fifo (let loop ()
                                           (let ([v2 (it)])
                                             (true! pred)
                                             (cond [(iter-eof? v2)  (values v2 '())]
                                                   [(not (pred v2)) (set! pred #f)
                                                                    (values v2 '())]
                                                   [else (let ([v3 f (loop)])
                                                           (values v3 (cons v2 f)))]
                                                   )))])
                            (set! itake-fifo (list->iter (cons v fifo)))
                            v4)
                          ]))
                 (begin0 vdrop
                         (set! vdrop iter-eof))))))

;; iter -> proc -> iter
(define (iter-filter pred? it)
  (lambda() (let loop ()
              (let ([v (it)])
                (if (iter-eof? v)
                    iter-eof
                    (if (pred? v)
                        v
                        (loop)))))))

; internal
; list<iter> -> list<any>
(define (read-iters its)
  (let loop ([r '()])
    (if (null? its)
        null
        (let ([v ((car its))])
          (and (not (iter-eof? v))
               (let ([rr (read-iters (cdr its))])
                 (and rr
                      (cons v rr))))))))

;; iter -> proc -> iter
(define (iter-filter-map proc . its)
  (lambda() (let loop ()
              (let ([vl (read-iters its)])
                (if vl
                    (or (apply proc vl)
                        (loop))
                    iter-eof)))))

;; proc -> iter -> iter
;; proc -> iter -> (iter ->)+ iter
(define (iter-map proc . its)
  (lambda() (let ([vl (read-iters its)])
              (if vl
                  (apply proc vl)
                  iter-eof))))

; iter up to first #f then return #f, otherwise return the last elem (#t for empty iter)
;; iter -> (values -> a) -> a|#t
(define (iter-every proc . its)
  (let loop ([last #t])
    (let ([vl (read-iters its)])
      (if vl
          (let ([r (apply proc vl)])
            (and r           ; (if r (loop r) #f)
                 (loop r)))
          last))))

; iter up to first (not #f) then return it, otherwise return the last elem (#f for empty iter)
;; iter -> (values -> a) -> a|#t
(define (iter-any proc . its)
  (let loop ([last #f])
    (let ([vl (read-iters its)])
      (if vl
          (let ([r (apply proc vl)])
            (or r
                (loop r)))
          last))))


;; iter -> proc -> ()
(define (iter-for-each proc it)
  (let loop ()
    (let ([v (it)])
      (unless (iter-eof? v)
        (proc v)
        (loop))))
  (void))

(define iter-o (curry iter-for-each o))

;; proc -> any -> iter -> any
;; proc -> any -> iter -> (iter ->)+ iter
(define (iter-fold proc init . its)
  (let loop ([init init])
    (let ([vl (read-iters its)])
      (if vl
          (loop (apply proc `(,@vl ,init)))
          init))))

;; proc -> any -> iter -> any
;; proc -> any -> iter -> (iter ->)+ iter
(define (iter-fold-right proc init . its)
  (let loop ()
    (let ([vl (read-iters its)])
      (if vl
          (apply proc `(,@vl ,(loop)))
          init))))

;; (a -> a -> a) -> a -> iter<a> -> a
;(define (iter-reduce proc ridentity it)
;  (let ([v (it)])
;    (if (iter-eof? v)
;        ridentity
;        (iter-fold proc v it))))

;; (a -> a -> a) -> a -> iter<a> -> a
(define (iter-reduce proc ridentity it)
  (let ([v (it)])
    (if (iter-eof? v)
        ridentity
        (let loop ([v v])
          (let ([v2 (it)])
            (if (iter-eof? v2)
                v
                (loop (proc v2 v))))))))

;; (a -> a -> a) -> a -> iter<a> -> a
(define (iter-reduce-right proc ridentity it)
  (let ([v (it)])
    (if (iter-eof? v)
        ridentity
        (let loop ([v v])
          (let ([v2 (it)])
            (if (iter-eof? v2)
                v
                (proc v (loop v2))))))))

; the minimum value
; (a -> a -> boolean) -> iter -> a|#f
(define (iter-min op< it)
  (iter-reduce (lambda(a b) (if (op< a b) a b)) #f it))

; the maximum value
; (a -> a -> boolean) -> iter -> a|#f
(define (iter-max op< it)
  (iter-reduce (lambda(a b) (if (op< a b) b a)) #f it))

; (a -> a -> boolean) -> iter -> number -> a|#f
;(define (iter-minn op< it n)
;  (true! (positive? n))
;  (let ([v (make-vector n)])
;    ; iter-for-eac (iter-take
;    (let loop1 ([i 0])
;      (if (< i n)
;          ; first stage, add all that incoming
;          (let ([x (it)])
;            (if (iter-eof? x)
;                ; iter length < n, return shorted vector
;                (vector-sort op< (vector-take v i))
;                (begin (vector-set! v i x)
;                       (loop1 (add1 i)))))
;          ; second stage
;          (begin (vector-sort! op< v)
;                 (iter-for-each (curry sorted-vector-insert! op< v) it)
;                 v)))))

; n minimum values
; (a -> a -> boolean) -> iter -> number -> a
(define (iter-minn op< it n)
  (true! (positive? n))
  (let ([v (make-vector n #f)])
    (let loop ([i 0])
      (let ([x (it)])
        (if (iter-eof? x)
            ; iter length < n, return shorter vector
            (if (< i n) (vector-take v i) v)
            (begin (sorted-vector-insert!
                    op< v x
                    0 (min n (add1 i)) ; mutable range
                    0 (min n i))       ; search range
                   (loop (add1 i))))))))

; n unique minimum values
; (a -> a -> integer) -> iter -> number -> a
(define (iter-minn-unique cmp it n)
  (true! (positive? n))
  (let ([v (make-vector n #f)])
    (let loop ([i 0])
      (let ([x (it)])
        (if (iter-eof? x)
            ; iter length < n, return shorter vector
            (if (< i n) (vector-take v i) v)
            (loop (+ i (if (sorted-vector-insert-unique!
                            cmp v x
                            0 (min n (add1 i))       ; mutable range
                            0 (min n i)) 1 0)))))))) ; search range

;; (iter ->)* iter
(define (iter-append . its)
  (lambda() (let loop ()
              (if (null? its)
                  iter-eof
                  (let ([v ((car its))])
                    (if (iter-eof? v)
                        (begin (pop! its)
                               (loop))
                        v))))))

(define (pair->mpair p)
  (mcons (car p) (cdr p)))

; last one is list of iterators
(define (iter-append* . its)
  (if (null? its)
      iter-eof
      (let ([its (pair->mpair its)])
        (lambda() (let loop ()
                    (if (null? (mcdr its))
                        ; last elem, (mcar its) is list
                        (if (null? (mcar its))
                            iter-eof
                            (let ([v ((car (mcar its)))])
                              (if (iter-eof? v)
                                  ; emit nothing, switch to next iter
                                  (begin (set-mcar! its (cdr (mcar its))) ; (pop! (mcar its))
                                         (loop))
                                  v)))
                        (let ([v ((mcar its))])
                          (if (iter-eof? v)
                              ; emit nothing, switch to next iter
                              (begin (set! its (pair->mpair (mcdr its)))
                                     (loop))
                              v))))))))

; classic: a random line from file in one pass
(define (iter-random-sample it [rdefault #f])
  (let loop ([i 0] [r rdefault])
    (let ([x (it)])
      (if (iter-eof? x)
          r
          (loop (add1 i) (if (= 0 (random-integer (add1 i))) x r))))))

; n non-unique random lines from file in one pass
(define (iter-random-samples n it)
  (let ([rv (make-vector n #f)])
    (let loop ([i 0])
      (let ([x (it)])
        (if (iter-eof? x)
            rv
            (begin (dotimes (j n)
                            (when (= 0 (random-integer (add1 i)))
                              (vector-set! rv j x)))
                   (loop (add1 i))))))))

; n unique random lines from file in one pass
(define (iter-random-samples-unique n it [keep-order #f])
  (let ([rv (make-vector n #f)])
    (let loop ([i 0])
      (let ([x (it)])
        (if (iter-eof? x)
            (if (< i n) (vector-take rv i) rv)
            (begin (if (< i n)
                       (vector-set! rv i x)
                       (let ([a (random-integer (add1 i))])
                         (when (< a n)
                           (if keep-order
                               (begin (vector-copy! rv a rv (add1 a))
                                      (vector-set! rv (sub1 n) x))
                               (vector-set! rv a x)))))
                   (loop (add1 i))))))))

;(iter->list (iter-take (lambda() (iter-random-samples-unique 5 (iter-iota 888) #t)) 6))
;(iter->list (iter-take (lambda() (iter-random-samples-unique 5 (iter-iota 888))) 6))
;(iter->list (iter-take (lambda() (iter-random-samples 5 (iter-iota 888))) 6))
;(iter->list (iter-take (lambda() (iter-random-sample (iter-iota 888))) 30))


; work in process. it is for walking directories recursively
(define (iter-recur it         ; starting iterator
                    godeeper?) ; value -> another iterator or false
  (let ([itstack (list it)])
    (lambda() (let loop()
                (if (null? itstack)
                    iter-eof
                    (let ([v ((car itstack))])
                      (if (iter-eof? v)
                          (begin (pop! itstack)
                                 (loop))
                          (let ([new-it (godeeper? v)])
                            (when new-it
                              (push! itstack new-it))
                            v))))))))


; (iter ->)+ -> iter
(define (iter-zip . its)
  (lambda() (or (read-iters its)
                iter-eof)))

;; parallel
; blocking
; endless? or until channel-poison?
(define (channel->iter ch)
  (cut channel-get ch))

; sent al iter values to a channel
;(define (iter-channel ch it)
;  (thread (lambda() (iter-for-each (cut channel-put ch <>) it)))
;  (void))

(define (iter-channel/oneeof ch it)
  (thread (lambda()
            (iter-for-each (cut channel-put ch <>) it)
            (channel-put ch iter-eof)))
  (void))

; TODO: limited number of eofs?

(define (iter-channel/eof-forever ch it)
  (thread (lambda()
            (let loop ()
              (let ([v (it)])
                (channel-put ch v)
                (loop)))))
  (void))

;(define ccc (make-channel))
;ccc
;(thread (lambda()          (iter-o (channel->iter ccc))          ))
;(iter-channel ccc (iter 1 2 3))
;(iter-channel ccc (iter 31 32 33))

; todo: max-treads
; !!!! test failed
(define (iter-parallel . its)
  (let ([ch (make-channel)]
        [n (length its)])
    (for-each (cut iter-channel/oneeof ch <>) its)

    ; it will eat n-1 eofs
    (lambda() (let loop ()
                (let ([v (channel-get ch)])
                  (if (iter-eof? v)
                      (if (< 1 n)
                          (begin (dec! n)
                                 (loop))
                          iter-eof)
                      v))))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; order not preserved
; iterator is called from different threads (bad with read-file..)
(define (iter-pmap/unsafe n proc it)
  (define ch (make-channel))
  ; start 'n' thread,
  ; each of them reads 'it', then apply 'proc' and send results to 'ch'
  (dotimes (_ n)
           (iter-channel/oneeof ch (iter-map proc it)))
  (lambda()
    (let loop ()
      (let ([v (channel-get ch)])
        (cond [(and (eq? v iter-eof) (= n 1)) iter-eof]
              [(eq? v iter-eof) (dec! n) (loop)]
              [else v])))))

(define (iter-syncronize it)
  (define ch (make-channel))
  ; reader thread
  (iter-channel/eof-forever ch it)
  (channel->iter ch))

(define (iter-pmap n proc it)
  (iter-pmap/unsafe n proc (iter-syncronize it)))

; for read read-string read-bytes-line read-bytes ...
(define (read->iter proc . args)
  (lambda()
    (let ([v (apply proc args)])
      (if (eof-object? v)
          iter-eof
          v))))

; iter<iter<v>> -> iter<v>
(define (iter-join iit)
  (let ([it #f])
    (lambda() (let loop()
                (cond [(iter-eof? it) iter-eof]
                      [(not it) (set! it (iit)) (loop)]
                      [else (let ([v (it)])
                              (if (iter-eof? v)
                                  (begin (set! it (iit)) (loop))
                                  v))])))))

; iter<a> -> (a -> iter<b>) -> iter<b>
(define (iter-bind it proc)
  (iter-join (iter-map proc it)))



; kinda reduce, apply proc pairwise, suitable for parallel map and merge
; (iter-bintree vector (iter-iota 10)) -> #(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) #(8 9))
; (iter-bintree cons (iter-iota 10) vector) ->  #(#(#((0 . 1) (2 . 3)) #((4 . 5) (6 . 7))) (8 . 9))
;; proc -> iter -> any
; TODO: no top-proc, but (level -> proc)
(define (iter->bintree proc it [top-proc proc])
  (let ([ia (it)])
    (if (iter-eof? ia)
        #f
        (let loop-right ([ia ia] [it it])
          (let ([ib (it)])
            (if (iter-eof? ib)
                ia
                (let loop-add-level ([level 1] [left (proc ia ib)])
                  (let ([ix (it)]) ; 2**n items processed, look ahead if one more level needed
                    (if (iter-eof? ix)
                        left
                        (let ([right (loop-right ix (iter-take it level))])
                          (loop-add-level (+ level level 1) (top-proc left right))))))))))))

(define (iter->tree it
                    [N0 '()]      ; empty node:    node
                    [N1 list]     ; terminal node: a -> node
                    [N3 vector])  ; regular node:  a -> left -> right -> node
  (let loop-right ([it it])
    (let ([left (it)])
      (if (iter-eof? left)
          N0
          (let loop-add-level ([level 1] [left (N1 left)])
            (let ([top (it)]) ; 2**n-1 items processed, look ahead if one more level needed
              (if (iter-eof? top)
                  left
                  (loop-add-level (+ level level 1)
                                  (N3 top left
                                      (loop-right (iter-take it level)))))))))))

; TODO: lazy version
; TODO?: unite cmp and join, like
; a -> b -> (list -1|0|1 (join a b))
(define (iter-merge cmp ia ib [join fst]) ; function to calc value when cmp=0
  (let ([a (ia)] [b (ib)]) ; move them inside lambda?
    (lambda() (cond
                ; TODO: set +inf to a/b after stream end to avoid iter-eof (for numeric iters)
                [(iter-eof? a) (begin0 b (set! b (ib))) ] ; a died
                [(iter-eof? b) (begin0 a (set! a (ia))) ] ; b died
                [else (if3 (cmp a b)
                           (begin0 a          (set! a (ia)))               ; emit a
                           (begin0 (join a b) (set! a (ia)) (set! b (ib))) ; emit both
                           (begin0 b          (set! b (ib))))]))))         ; emit b

;(define (iter-union cmp ia ib)
;    (iter-merge cmp ia ib fst))

(define (iter-intersection cmp ia ib [join fst])
  (let ([a (ia)] [b (ib)]) ; move them inside lambda?
    (lambda() (let loop ()
                (cond
                  [(iter-eof? a) iter-eof] ; a died
                  [(iter-eof? b) iter-eof] ; b died
                  [else (if3 (cmp a b)
                             (begin             (set! a (ia)) (loop))
                             (begin0 (join a b) (set! a (ia)) (set! b (ib))) ; emit
                             (begin             (set! b (ib)) (loop)))])))))

;; proc -> iter<iter<v>> -> iter<v>
(define (iter-merge* cmp it [join fst])
  (iter->bintree (lambda(ia ib)(iter-merge cmp ia ib join)) it))


;; proc -> vector<iter<v>> -> iter<v>
(define (iter-mergev cmp ivec [join fst]
                     [start 0]
                     [stop (vector-length ivec)] )
  (case (- stop start)
    [(0) (iter)] ; empty
    [(1) (vector-ref ivec start)]
    ;   [(2) (iter-merge cmp (vector-ref ivec start) (vector-ref ivec (+ 1 start)) join)]
    [else (let ([p (quotient (+ stop start) 2)])
            (iter-merge cmp
                        (iter-mergev cmp ivec join start p)
                        (iter-mergev cmp ivec join p stop)
                        join))]))

; TODO: optimized iter-merge, with sorted contained inside
; the presend recursive versions create (N-1) closures


; list -> iter
;(define (list->iter-cycle lst)

; TODO: (define-generator yield
; 1. can accept lambda (no break)
; 2. can return iterator (can break? how to finalize?)


; +TESTS

(define (test-iter l)
  (let ([v (l)]) (equal! 1 v))
  (let ([v (l)]) (equal! 2 v))
  (let ([v (l)]) (equal! 5 v))
  (let ([v (l)]) (equal! 6 v))
  (let ([v (l)]) (equal! 7 v))
  (let ([v (l)]) (true! (iter-eof? v)))
  (let ([v (l)]) (true! (iter-eof? v))))


(test-iter (iter 1 2 5 6 7))
(test-iter (list->iter (list 1 2 5 6 7)))
(test-iter (vector->iter (vector 1 2 5 6 7)))
(test-iter (bytes->iter (bytes 1 2 5 6 7)))
(test-iter (string->iter-ord "\1\2\5\6\7"))

(equal! (iter->list (string->iter "hello")) '(#\h #\e #\l #\l #\o))

(equal! (iter->list (iter-take (string->iter "hello") -1)) '())
(equal! (iter->list (iter-take (string->iter "hello") 0))  '())
(equal! (iter->list (iter-take (string->iter "hello") 1))  '(#\h))
(equal! (iter->list (iter-take (string->iter "hello") 3))  '(#\h #\e #\l))
(equal! (iter->list (iter-take (string->iter "hello") 10)) '(#\h #\e #\l #\l #\o))

(equal! (iter->list (iter-drop     (string->iter "hello") -1)) '(#\h #\e #\l #\l #\o)
        (iter->list (iter-drop/now (string->iter "hello") -1)) '(#\h #\e #\l #\l #\o))
(equal! (iter->list (iter-drop     (string->iter "hello") 0))  '(#\h #\e #\l #\l #\o)
        (iter->list (iter-drop/now (string->iter "hello") 0))  '(#\h #\e #\l #\l #\o))
(equal! (iter->list (iter-drop     (string->iter "hello") 3))  '(#\l #\o)
        (iter->list (iter-drop/now (string->iter "hello") 3))  '(#\l #\o))
(equal! (iter->list (iter-drop     (string->iter "hello") 5))  '()
        (iter->list (iter-drop/now (string->iter "hello") 5))  '())
(equal! (iter->list (iter-drop     (string->iter "hello") 10)) '()
        (iter->list (iter-drop/now (string->iter "hello") 10)) '())

(equal! '(3 8 13 18 23 28)
        (iota 6 3 5)
        (iter->list (iter-range 3 30 5))
        (iter->list (iter-iota 6 3 5))
        (iter->rlist (iter-iota 6 28 -5))
        (build-list 6 (lambda(i) (+ 3 (* 5 i))))
        (iter->list (build-iter 6 (lambda(i) (+ 3 (* 5 i))))))

(equal! (list* 1 2 (list 3 4))
        (list* (list 1 2 3 4))
        (iter->list (iter* (iter 1 2 3 4)))
        (iter->list (iter* 1 2 (iter 3 4))))

(equal!  '(1 2 3 4 5 6 7 8 9 10)
         (iter->list
          (iter-take (iter-map add1 (iter-iota 100)) 10))
         (      take (     map add1 (     iota 100)) 10))


(equal!
 (iter->list
  (iter-take (iter-map + (iter-iota 3) (iter-iota 3 1000 100)) 10))
 ;(      take (     map + (     iota 3) (     iota 3 1000 100)) 10)
 '(1000 1101 1202))

; srfi/1 map, allow inequal length
(equal!
 (iter->list
  (iter-map + (iter-iota 3) (iter-iota 10 1000 100)))
 (iter->list
  (iter-map + (iter-iota 10 1000 100) (iter-iota 3)))
 (     map + (     iota 3) (     iota 10 1000 100))
 '(1000 1101 1202))

(equal!
 (iter->list
  (iter-take (iter-map + (iter-iota 200) (iter-iota 100 1000 100)) 10))
 (      take (     map + (     iota 200) (     iota 100 1000 100)) 10)
 '(1000 1101 1202 1303 1404 1505 1606 1707 1808 1909))

; iter-fold
(equal! (iter-fold +      666 (iter-iota 0))
        (     fold +      666 (     iota 0)))
(equal! (iter-fold -      666 (iter-iota 0))
        (     fold -      666 (     iota 0)))
(equal! (iter-fold cons   666 (iter-iota 0))
        (     fold cons   666 (     iota 0)))
(equal! (iter-fold +      666 (iter-iota 10))
        (     fold +      666 (     iota 10)))
(equal! (iter-fold -      666 (iter-iota 10))
        (     fold -      666 (     iota 10)))
(equal! (iter-fold cons   666 (iter-iota 10))
        (     fold cons   666 (     iota 10)))
(equal! (iter-fold +      666 (iter-iota 10) (iter-iota 10 5 10))
        (     fold +      666 (     iota 10) (     iota 10 5 10)))
(equal! (iter-fold -      666 (iter-iota 10) (iter-iota 10 5 10))
        (     fold -      666 (     iota 10) (     iota 10 5 10)))
(equal! (iter-fold vector 666 (iter-iota 10) (iter-iota 10 5 10))
        (     fold vector 666 (     iota 10) (     iota 10 5 10))
        (iter-fold vector 666 (iter-iota 10) (iter-iota 20 5 10))
        (     fold vector 666 (     iota 10) (     iota 20 5 10)))

; iter-fold-right
(equal! (iter-fold-right +      666 (iter-iota 0))
        (     fold-right +      666 (     iota 0)))
(equal! (iter-fold-right -      666 (iter-iota 0))
        (     fold-right -      666 (     iota 0)))
(equal! (iter-fold-right cons   666 (iter-iota 0))
        (     fold-right cons   666 (     iota 0)))
(equal! (iter-fold-right +      666 (iter-iota 10))
        (     fold-right +      666 (     iota 10)))
(equal! (iter-fold-right -      666 (iter-iota 10))
        (     fold-right -      666 (     iota 10)))
(equal! (iter-fold-right cons   666 (iter-iota 10))
        (     fold-right cons   666 (     iota 10)))
(equal! (iter-fold-right +      666 (iter-iota 10) (iter-iota 10 5 10))
        (     fold-right +      666 (     iota 10) (     iota 10 5 10)))
(equal! (iter-fold-right -      666 (iter-iota 10) (iter-iota 10 5 10))
        (     fold-right -      666 (     iota 10) (     iota 10 5 10)))
(equal! (iter-fold-right vector 666 (iter-iota 10) (iter-iota 10 5 10))
        (     fold-right vector 666 (     iota 10) (     iota 10 5 10))
        (iter-fold-right vector 666 (iter-iota 10) (iter-iota 20 5 10))
        (     fold-right vector 666 (     iota 10) (     iota 20 5 10)))

; iter-reduce
(equal! (iter-reduce +      666 (iter-iota 0))
        (     reduce +      666 (     iota 0)))
(equal! (iter-reduce -      666 (iter-iota 0))
        (     reduce -      666 (     iota 0)))
(equal! (iter-reduce cons   666 (iter-iota 0))
        (     reduce cons   666 (     iota 0)))
(equal! (iter-reduce +      666 (iter-iota 10))
        (     reduce +      666 (     iota 10)))
(equal! (iter-reduce -      666 (iter-iota 10))
        (     reduce -      666 (     iota 10)))
(equal! (iter-reduce cons   666 (iter-iota 10))
        (     reduce cons   666 (     iota 10)))

; iter-reduce-right
(equal! (iter-reduce-right +      666 (iter-iota 0))
        (     reduce-right +      666 (     iota 0)))
(equal! (iter-reduce-right -      666 (iter-iota 0))
        (     reduce-right -      666 (     iota 0)))
(equal! (iter-reduce-right cons   666 (iter-iota 0))
        (     reduce-right cons   666 (     iota 0)))
(equal! (iter-reduce-right +      666 (iter-iota 10))
        (     reduce-right +      666 (     iota 10)))
(equal! (iter-reduce-right -      666 (iter-iota 10))
        (     reduce-right -      666 (     iota 10)))
(equal! (iter-reduce-right cons   666 (iter-iota 10))
        (     reduce-right cons   666 (     iota 10)))

; iter-min
(=!   0 (iter-min < (iter 34 52 1 51 92 91 1 0 6 100 92 2)))

; iter-max
(=! 100 (iter-max < (iter 34 52 1 51 92 91 1 0 6 100 92 2)))

; iter-minn
(define iter-min-nums (curry iter-minn <))
(define iter-max-nums (curry iter-minn >))
(define iter-min-nums-unique (curry iter-minn-unique number-compare))
(define iter-max-nums-unique (curry iter-minn-unique (compose - number-compare)))

(equal! (map (lambda(i) (iter-min-nums (iter 34 52 1 51 92 91 1 0 6 100 92 2) (+ 0 i)))
             (iota 15 1))
        '(#(0)
          #(0 1)
          #(0 1 1)
          #(0 1 1 2)
          #(0 1 1 2 6)
          #(0 1 1 2 6 34)
          #(0 1 1 2 6 34 51)
          #(0 1 1 2 6 34 51 52)
          #(0 1 1 2 6 34 51 52 91)
          #(0 1 1 2 6 34 51 52 91 92)
          #(0 1 1 2 6 34 51 52 91 92 92)
          #(0 1 1 2 6 34 51 52 91 92 92 100)
          #(0 1 1 2 6 34 51 52 91 92 92 100)
          #(0 1 1 2 6 34 51 52 91 92 92 100)
          #(0 1 1 2 6 34 51 52 91 92 92 100)))
(equal! (map (lambda(i) (iter-max-nums (iter 34 52 1 51 92 91 1 0 6 100 92 2) (+ 0 i)))
             (iota 15 1))
        '(#(100)
          #(100 92)
          #(100 92 92)
          #(100 92 92 91)
          #(100 92 92 91 52)
          #(100 92 92 91 52 51)
          #(100 92 92 91 52 51 34)
          #(100 92 92 91 52 51 34 6)
          #(100 92 92 91 52 51 34 6 2)
          #(100 92 92 91 52 51 34 6 2 1)
          #(100 92 92 91 52 51 34 6 2 1 1)
          #(100 92 92 91 52 51 34 6 2 1 1 0)
          #(100 92 92 91 52 51 34 6 2 1 1 0)
          #(100 92 92 91 52 51 34 6 2 1 1 0)
          #(100 92 92 91 52 51 34 6 2 1 1 0)))

(equal! (map (lambda(i) (iter-min-nums-unique (iter 34 52 1 51 92 91 1 0 6 100 92 2) (+ 0 i)))
             (iota 11 1))
        '(#(0)
          #(0 1)
          #(0 1 2)
          #(0 1 2 6)
          #(0 1 2 6 34)
          #(0 1 2 6 34 51)
          #(0 1 2 6 34 51 52)
          #(0 1 2 6 34 51 52 91)
          #(0 1 2 6 34 51 52 91 92)
          #(0 1 2 6 34 51 52 91 92 100)
          #(0 1 2 6 34 51 52 91 92 100)))

(equal! (map (lambda(i) (iter-max-nums-unique (iter 34 52 1 51 92 91 1 0 6 100 92 2) (+ 0 i)))
             (iota 11 1))
        '(#(100)
          #(100 92)
          #(100 92 91)
          #(100 92 91 52)
          #(100 92 91 52 51)
          #(100 92 91 52 51 34)
          #(100 92 91 52 51 34 6)
          #(100 92 91 52 51 34 6 2)
          #(100 92 91 52 51 34 6 2 1)
          #(100 92 91 52 51 34 6 2 1 0)
          #(100 92 91 52 51 34 6 2 1 0)))

; iter->tree
(equal! (build-list 10 (lambda(i) (iter->tree (iter-iota i))))
        '(()
          (0)
          #(1 (0) ())
          #(1 (0) (2))
          #(3 #(1 (0) (2)) ())
          #(3 #(1 (0) (2)) (4))
          #(3 #(1 (0) (2)) #(5 (4) ()))
          #(3 #(1 (0) (2)) #(5 (4) (6)))
          #(7 #(3 #(1 (0) (2)) #(5 (4) (6))) ())
          #(7 #(3 #(1 (0) (2)) #(5 (4) (6))) (8))))
(equal! (build-list 10 (lambda(i) (iter->tree (iter-iota i) #f identity list)))
        '(#f
          0
          (1 0 #f)
          (1 0 2)
          (3 (1 0 2) #f)
          (3 (1 0 2) 4)
          (3 (1 0 2) (5 4 #f))
          (3 (1 0 2) (5 4 6))
          (7 (3 (1 0 2) (5 4 6)) #f)
          (7 (3 (1 0 2) (5 4 6)) 8)))

; iter->bintree
(equal! (iter->list (iter-map
                     (lambda(i)(iter->bintree vector (iter-iota i)))
                     (iter-iota 18)))
        '(#f
          0
          #(0 1)
          #(#(0 1) 2)
          #(#(0 1) #(2 3))
          #(#(#(0 1) #(2 3)) 4)
          #(#(#(0 1) #(2 3)) #(4 5))
          #(#(#(0 1) #(2 3)) #(#(4 5) 6))
          #(#(#(0 1) #(2 3)) #(#(4 5) #(6 7)))
          #(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) 8)
          #(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) #(8 9))
          #(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) #(#(8 9) 10))
          #(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) #(#(8 9) #(10 11)))
          #(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) #(#(#(8 9) #(10 11)) 12))
          #(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) #(#(#(8 9) #(10 11)) #(12 13)))
          #(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) #(#(#(8 9) #(10 11)) #(#(12 13) 14)))
          #(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) #(#(#(8 9) #(10 11)) #(#(12 13) #(14 15))))
          #(#(#(#(#(0 1) #(2 3)) #(#(4 5) #(6 7))) #(#(#(8 9) #(10 11)) #(#(12 13) #(14 15)))) 16)))

(equal! (map (lambda(i)(iter->bintree + (iter-iota i) vector))
             (iota 18))
        '(#f
          0
          1
          #(1 2)
          #(1 5)
          #(#(1 5) 4)
          #(#(1 5) 9)
          #(#(1 5) #(9 6))
          #(#(1 5) #(9 13))
          #(#(#(1 5) #(9 13)) 8)
          #(#(#(1 5) #(9 13)) 17)
          #(#(#(1 5) #(9 13)) #(17 10))
          #(#(#(1 5) #(9 13)) #(17 21))
          #(#(#(1 5) #(9 13)) #(#(17 21) 12))
          #(#(#(1 5) #(9 13)) #(#(17 21) 25))
          #(#(#(1 5) #(9 13)) #(#(17 21) #(25 14)))
          #(#(#(1 5) #(9 13)) #(#(17 21) #(25 29)))
          #(#(#(#(1 5) #(9 13)) #(#(17 21) #(25 29))) 16)))

; iter-merge*
; iter-mergev
(equal! '(1 2 3 4 5 6 8 9 100 200 300 301 302 400)
        (iter->list (iter-merge*
                     integer-compare (iter (iter 1 3 5 6 100)
                                           (iter 2 3 6 9 200)
                                           (iter 3 4 5 8 9 300)
                                           (iter 3 4 5 8 9 301)
                                           (iter 3 4 5 8 9 302)
                                           (iter 2 3 4 6 9 400))))
        (iter->list (iter-mergev
                     integer-compare (vector (iter 1 3 5 6 100)
                                             (iter 2 3 6 9 200)
                                             (iter 3 4 5 8 9 300)
                                             (iter 3 4 5 8 9 301)
                                             (iter 3 4 5 8 9 302)
                                             (iter 2 3 4 6 9 400)))))

; iter-length
(=! 0 (iter-length (build-iter 0 values)))
(=! 1 (iter-length (build-iter 1 values)))
(=! 10000 (iter-length (build-iter 10000 values)))

; iter-filter
(equal! (filter even? (iota 10))
        (iter->list (iter-filter even? (iter-iota 10))))
(equal! (filter odd? (iota 10))
        (iter->list (iter-filter odd? (iter-iota 10))))

; iter-filter-map
(equal! (filter-map (lambda(x) (and (even? x) (* x 2))) (iota 10))
        (iter->list (iter-filter-map (lambda(x) (and (even? x) (* x 2))) (iter-iota 10))))
(equal! (filter-map (lambda (x y) (and (positive? x) (positive? y) (list x y (+ x y))))
                    '(1  2 3 -2  8 -1 0)
                    '(1 -2 3 -2 -8  0 0))
        (iter->list (iter-filter-map (lambda (x y) (and (positive? x) (positive? y) (list x y (+ x y))))
                                     (iter 1  2 3 -2  8 -1 0)
                                     (iter 1 -2 3 -2 -8  0 0))))


; iter-every
(equal! 10
        (every + '(1 2 3) '(7 8))
        (iter-every + (iter 1 2 3) (iter 7 8)))
(equal! 4
        (every add1 '(1 2 3))
        (iter-every add1 (iter 1 2 3)))
(equal! #f
        (every even? '(1 2 3))
        (iter-every even? (iter 1 2 3)))
(equal! #t
        (every even? '(0 2 6))
        (iter-every even? (iter 0 2 6)))
(equal! #t
        (every add1 '())
        (iter-every add1 (iter)))

; iter-any
(equal! 8
        (any + '(1 2 3) '(7 8))
        (iter-any + (iter 1 2 3) (iter 7 8)))
(equal! 2
        (any add1 '(1 2 3))
        (iter-any add1 (iter 1 2 3)))
(equal! #t
        (any even? '(1 2 3))
        (iter-any even? (iter 1 2 3)))
(equal! #f
        (any odd? '(0 2 6))
        (iter-any odd? (iter 0 2 6)))
(equal! #f
        (any add1 '())
        (iter-any add1 (iter)))

(equal! #t
        (any integer? '(a 3 b 2.7))
        (iter-any integer? (iter 'a 3 'b 2.7)))
(equal! #f
        (any integer? '(a 3.1 b 2.7))
        (iter-any integer? (iter 'a 3.1 'b 2.7)))
(equal! #t
        (any < '(3 1 4 1 5) '(2 7 1 8 2))
        (iter-any < (iter 3 1 4 1 5) (iter 2 7 1 8 2)))


; iter-append
(equal!
 (iter->list
  (iter-append
   (iter-iota 0)
   (iter-iota 10)
   (iter-iota 0)
   (iter-iota 10 1000)
   (iter-iota 0)))
 (iter->list
  (iter-append
   (iter-iota 10)
   (iter-iota 10 1000)))
 (append
  (iota 10)
  (iota 10 1000)))

; iter-append*
(equal! (iter->list (iter-append* (iter 'a) (iter 'b) (list (iter 'c) (iter 'd) (iter 'e))))
        (iter->list (iter-append* (iter 'a 'b 'c) (iter 'd 'e) '()))
        (iter->list (iter-append* (list (iter 'a 'b) (iter 'c 'd 'e))))

        (append* '(a) '(b) '((c)(d)(e)))
        (append* '(a b c) '(d e) '())
        (append* '((a b) (c d e))))

(equal! (append* '())
        (iter->list (iter-append* '())))

; iter-parallel
(=! 50 (iter-length
        (iter-parallel (iter-iota 10 1)
                       (iter-iota 10 2)
                       (iter-iota 10 10)
                       (iter-iota 10 100)
                       (iter-iota 10 1000))))
; iter-zip
(equal! (iter->list (iter-zip (iter 1 2 3)) )
        (zip (list 1 2 3))
        '((1) (2) (3)))
(equal! (zip (list 'one 'two 'three)
             (list 1 2 3)
             (list 'odd 'even 'odd 'even 'odd 'even 'odd 'even))
        (iter->list (iter-zip (iter 'one 'two 'three)
                              (iter 1 2 3)
                              (iter 'odd 'even 'odd 'even 'odd 'even 'odd 'even)))
        '((one 1 odd) (two 2 even) (three 3 odd)))


; iter-take-while
(equal! (take-while even? '(2 18 3 10 22 9)) ;=> (2 18)
        (iter->list (iter-take-while even? (iter 2 18 3 10 22 9))))

; iter-drop-while
(equal! (drop-while even? '(2 18 3 10 22 9)) ;=> (3 10 22 9)
        (iter->list (iter-drop-while     even? (iter 2 18 3 10 22 9)))
        (iter->list (iter-drop-while/now even? (iter 2 18 3 10 22 9))))

; iter-index
(equal! (list-index even? '(3 1 4 1 5 9)) ;=> 2
        (iter-index even? (iter 3 1 4 1 5 9)))
(equal! (list-index string? '(3 1 4 1 5 9))
        (iter-index string? (iter 3 1 4 1 5 9)))

(equal! (list-index < '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) ;=> 1
        (iter-index < (iter 3 1 4 1 5 9 2 5 6) (iter 2 7 1 8 2)))
(equal! (list-index = '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) ;=> #f
        (iter-index = (iter 3 1 4 1 5 9 2 5 6) (iter 2 7 1 8 2)))


(equal! '(1 2 4 9 13 20)
        (iter->list (iter-intersection integer-compare
                                       (iter 1 2 4 5 9 12 13 20 30)
                                       (iter 1 2 3 4 9 13 14 20 32))))



(let ([i1 i2 (iter-span even? (iter 2 4 6 8 18 3 10 22 9))])
  (equal! (iter->list i2) '(3 10 22 9))
  (equal! (iter->list i1) '(2 4 6 8 18)))
(let ([i1 i2 (iter-span even? (iter 2 4 6 8 18 3 10 22 9))])
  (equal! (iter->list i1) '(2 4 6 8 18))
  (equal! (iter->list i2) '(3 10 22 9)))

#|
;;;;
(require scheme/generator)
(define g (generator
                (let loop ([x '(a b c)])
                  (unless (null? x)
                      (yield (car x))
                      (loop (cdr x))))
                iter-eof
                ))
(g)

(for/list ([i (in-producer (iter 1 2 3) iter-eof)])
      i)
;(for/list ([i (in-generator (iter 1 2 3 (void)))])
;      i)
|#